package com.tgy.algorithm.base._二叉树;

class BiNodeDistanceInfo {
    int maxDistance;
    int height;
    public BiNodeDistanceInfo(int maxDistance, int height) {
        this.maxDistance = maxDistance;
        this.height = height;
    }
}

public class _查找二叉树两个节点之间最大距离 {

    public static BiTreeNode generalBiTreeNode() {
        /**
         *              1
         *         2           3
         *      4     5     6
         *          7
         */
        BiTreeNode root = new BiTreeNode(1);
        root.left = new BiTreeNode(2);
        root.right = new BiTreeNode(3);
        root.left.left = new BiTreeNode(4);
        root.left.right = new BiTreeNode(5);
        root.right.left = new BiTreeNode(6);
        root.left.right.left = new BiTreeNode(7);
        return root;
    }



    public static int nodeMaxDistance(BiTreeNode root) {
        return doNodeMaxDistance(root).maxDistance;
    }

    public static BiNodeDistanceInfo doNodeMaxDistance(BiTreeNode root) {

        if (root == null) {
            return new BiNodeDistanceInfo(0,0);
        }

        BiNodeDistanceInfo leftInfo = doNodeMaxDistance(root.left);
        BiNodeDistanceInfo rightInfo = doNodeMaxDistance(root.right);

        // 与root无关
        int maxDistance = Math.max(leftInfo.maxDistance, rightInfo.maxDistance);
        // 与root有关
        maxDistance = Math.max(leftInfo.height + 1 + rightInfo.height,maxDistance);
        BiNodeDistanceInfo retInfo = new BiNodeDistanceInfo(maxDistance, Math.max(leftInfo.height,rightInfo.height) + 1);
        return retInfo;
    }


    public static void main(String[] args) {
        BiTreeNode root = generalBiTreeNode();
        int maxDistance = nodeMaxDistance(root);
        System.out.println(maxDistance);
    }
}
